package com.example.demo.Class25_singleStack;
/**
 * 单调栈
 * 一个数组，输出 任意一个数字 左右两边 最近的 比自身小的值。
 * [3,4,2,6,1,7,0,5] 没有重复值！
 *
 * 1->2 : 代表 数组index = 1   value = 2
 * 保持：栈顶放入最大值 栈底最小值 排列
 *              本位点        左边最小        右边最小
 * 待加入的点    将要弹出的点  待弹出下面的点     待加入的点
 * adding       pop         peek           adding
 * 2->2         1->4        0->3            2->2
 * 2->2         0->3        -1              2->2
 * 4->1         3->6        2->2            4->1
 * 4->1         2->2        -1              4->1
 * 6->0         5->7        4->1            6->0
 * 6->0         4->1        -1              6->0
 * 空栈继续弹     7->5        6->0            -1
 *              6->0        -1              -1
 *
 *
 * ------具有重复值的单调栈如何处理-------------------------------------
 * value:[1,3,4,5,4,3,1,2]
 * index:[0,1,2,3,4,5,6,7]
 * 进栈 过程 进栈符合 进栈排序规则 ，大栈顶 小栈底
 * |{3}->5|
 * |{2}->4|
 * |{1}->3|
 * |{0}->1|
 * ——————————
 * 当进入 4->4时候，涉及到弹栈
 * 弹出 {3}->5 符合没有重复值的单调栈
 * 再压入4->4的时候，形式如{2,4}->4 规则：后进入的放入索引结尾节点
 *
 *                  adding        pop       peek        adding
 * |{2，3}->4|       4->4        3->5        1->3        4->4
 * |{1  }->3|
 * |{0  }->1|
 * ——————————
 *
 *                  adding        pop       peek        adding
 *                   4->4        3->5        1->3        4->4
 *  压入5-3时，先弹出 4->4
 *                   5->3       4->4        1->3        5->3
 *                   5->3       2->4        1->3        5->3
 * |{2，4}->4|
 * |{1  }->3|
 * |{0  }->1|
 * ——————————
 *
 *                  adding        pop       peek        adding
 *                   4->4        3->5        1->3        4->4
 *  压入5-3时，先弹出 4->4
 *                   5->3       4->4        1->3        5->3
 *                   5->3       2->4        1->3        5->3
 * |{1,5}->3|
 * |{0  }->1|
 * ——————————
 *
 *
 *
 *                  adding        pop       peek        adding
 *                   4->4        3->5        1->3        4->4
 *  压入5-3时，先弹出 4->4
 *                   5->3       4->4        1->3        5->3
 *                   5->3       2->4        1->3        5->3
 * 压入6->1 时
 *                   6->1       5->3        0->1        6->1
 *                   6->1       1->3        0->1        6->1
 * |{1,5}->3|
 * |{0  }->1|
 * ——————————
 * |{0,6}->1|
 * ——————————
 *
 *
 *
 *                  adding        pop       peek        adding
 *                   4->4        3->5        1->3        4->4
 *  压入5-3时，先弹出 4->4
 *                   5->3       4->4        1->3        5->3
 *                   5->3       2->4        1->3        5->3
 * 压入6->1 时
 *                   6->1       5->3        0->1        6->1
 *                   6->1       1->3        0->1        6->1
 * |{1,5}->3|
 * |{0  }->1|
 * ——————————
 * 压入7->2 时候
 * |{7} ->2 |                   7->2       6->1         -1
 * |{0,6}->1|
 * ——————————
 *
 *
 *
 *
 *
 *                  adding        pop       peek        adding
 *                   4->4        3->5        1->3        4->4
 *  压入5-3时，先弹出 4->4
 *                   5->3       4->4        1->3        5->3
 *                   5->3       2->4        1->3        5->3
 * 压入6->1 时
 *                   6->1       5->3        0->1        6->1
 *                   6->1       1->3        0->1        6->1
 * |{1,5}->3|
 * |{0  }->1|
 * ——————————
 * 压入7->2 时候,并弹出
 * |{7} ->2 |                   7->2       6->1         -1
 * 弹出 {0,6}->1
 * |{0,6}->1|                   6->1       -1           -1
 * |{0,6}->1|                   0->1       -1          -1
 * ——————————
 *
 */